package com.Sep_Twellve;

import com.Sep_Nine.Solution112;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(0,preorder.length-1,0,inorder.length-1,preorder,inorder);
    }

    public TreeNode dfs(int leftPre,int rightPre,int leftIn,int rightIn,int[] pre,int[] in){
        if (leftIn>rightIn) return null;
        TreeNode root=new TreeNode(pre[leftPre]);
        int rootIn=leftIn;
        while(rootIn<=rightIn&&in[rootIn]!=pre[leftPre]) rootIn++;
        int left=rootIn-leftIn;
        root.left=dfs(leftPre+1,leftPre+left-1,leftIn,rootIn-1,pre,in);
        root.right=dfs(leftPre+left+1,rightPre,rootIn+1,rightIn,pre,in);
        return root;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
